package com.itheima.leetcode.od.b.greedy;

import java.util.Arrays;

/**
 * (B卷,200分)- 观看文艺汇演问题（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 为了庆祝中国共产党成立100周年，某公园将举行多场文艺表演，很多演出都是同时进行，一个人只能同时观看一场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有15分钟的时间间隔，
 * <p>
 * 小明是一个狂热的文艺迷，想观看尽可能多的演出， 现给出演出时间表，请帮小明计算他最多能观看几场演出。
 * <p>
 * 输入描述
 * <p>
 * 第一行为一个数N，表示演出场数，1<=N<=1000，接下来N行，每行有被空格分割的两个整数，
 * <p>
 * 第一个整数T表示演出的开始时间，第二个整数L表示演出的持续时间，T和L的单位为分钟，0<=T<=1440,0<L<=100.
 * <p>
 * 输出描述
 * <p>
 * 输出最多能观看的演出场数。
 * <p>
 * 用例
 * <p>
 * 输入	2
 * <p>
 * 720 120
 * <p>
 * 840 120
 * <p>
 * 输出	1
 * <p>
 * 说明	两场演出间隔时间为0，不满足最小15分钟时间间隔的要求，所以最多只能观看一场演出
 * <p>
 * 输入	2
 * <p>
 * 0 60
 * <p>
 * 90 60
 * <p>
 * 输出	2
 * <p>
 * 说明	两场演出间隔大于15分钟，都能观看到
 */
public class WatchPerformances {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt(); // 开始时间
            ranges[i][1] = ranges[i][0] + sc.nextInt(); // 结束时间 = 开始时间 + 持续时间
        }*/

        int n = 2;
        int[][] ranges = new int[n][2];
        ranges[0][0] = 720;
        ranges[0][1] = ranges[0][0] + 120;
        ranges[1][0] = 840;
        ranges[1][1] = ranges[1][0] + 120;
        System.out.println(getResult(ranges));
        System.out.println(eraseOverlapIntervals(ranges));
    }

    /**
     * 贪心求解
     *
     * @param ranges
     * @return
     */
    public static int getResult(int[][] ranges) {
        Arrays.sort(ranges, (a, b) -> a[1] - b[1]); // 升序排序

        int t = ranges[0][1];
        int ans = 1;

        for (int i = 1; i < ranges.length; i++) {
            int l = ranges[i][0];
            int r = ranges[i][1];

            if (l - t >= 15) {
                ans++;
                t = r;
            }
        }

        return ans;
    }

    /**
     * 动态规划
     *
     * @param ranges
     * @return
     */
    public static int eraseOverlapIntervals(int[][] ranges) {
        if (ranges.length == 0) {
            return 0;
        }

        Arrays.sort(ranges, (interval1, interval2) -> interval1[0] - interval2[0]);

        int n = ranges.length;
        int[] f = new int[n]; // 数组记录第n个可以达到的最大不相交区间的个数
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (ranges[j][1] + 15 <= ranges[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }
}